package com.lun.swordtowardoffer2.c04;

import com.lun.util.SinglyLinkedList.ListNode;

public class IsPalindrome {
	
	
	private static final ReverseList RL = new ReverseList();

	public boolean isPalindrome(ListNode head) {
		if(head == null) return false;
		
		ListNode slow = head, prev = null;
		ListNode fast = slow.next;
		
		while(fast != null) {
			prev = slow;
			slow = slow.next;
			fast = fast.next;
			if(fast != null)
				fast = fast.next;
		}
		if(prev != null)
			prev.next = null;//断链
		
		return equals(head, RL.reverseList(slow));
	}
	
	private boolean equals(ListNode head1, ListNode head2) {
		if(head1 != null && head2 != null) {
			if(head1.val != head2.val) {
				return false;
			}
			return equals(head1.next, head2.next);
		}
		
		return true;
	}
}
